(1) Field of the Invention
The present invention pertains generally to encoding of pictorial data and, in particular, to encoding of two level (black and white) facsimile pictures using run length encoding.
(2) Description of the Prior Art
In U.S. Pat. No. 4,060,834 issued to F. W. Mounts and A. N. Netravali on Nov. 29, 1977, a processor for increasing the run length of digital signals is described wherein a signal measure is permuted in response to a reference signal. As applied in the context of facsimile picture encoding, the signal measure is an error signal generated by predicting the intensity value of each element of the picture based upon the intensity values of surrounding picture elements, and by comparing the prediction so generated with the actual intensity value of the picture element. The reference signal, sometimes referred to as a calibration signal, is a measure of the degree of confidence associated with each prediction. Each line of picture data (or data from any other convenient reordering interval) is processed so that if the prediction is considered "good", the error signal is loaded beginning at one end of a memory while, if the prediction is "bad", the error is loaded beginning at the opposite end of the memory. The permuted or reordered error signal, when read sequentially from one end of the memory, then statistically exhibits runs of increased length, since, in the good region, errors should seldom be encountered. Accordingly, the reordered signal can be processed with increased efficiency in a conventional run-length encoder.
While the Mounts et al invention achieves significant improvement in encoding efficiency for facsimile pictures, a further decrease in bit rate is nevertheless possible. Accordingly, the broad object of the present invention is to decrease the amount of data which must be used to represent a two-tone picture without degrading its quality. By so doing, it becomes possible to capitalize on the trend in which the cost of digital circuits and memories is decreasing faster than the cost of transmission facilities. A concomitant object is to make further use of the redundancy contained in most pictures in order to reduce the number of bits per picture element that must be communicated between transmitter and receiver, or that must be stored so as to permit later recovery of the picture.